HJ62 查找输入整数二进制中1的个数

本节目标：理解“HJ62 查找输入整数二进制中1的个数”的核心思路，并能把它用于实际开发或面试表达。 简单 通过率：44.78% 时间限制：1秒 空间限制：32M 知识点==位运算== 描述 输入一个正整数，计算它在二进制下的1的个数。 注意多组输入输出！！！！！！

数据范围： 1≤�≤231−1 1≤n≤231−1 输入描述： 输入一个整数 输出描述： 计算整数二进制中1的个数 示例1 输入： 5 ==复制== 输出： 2 ==复制== 说明： 5的二进制表示是101，有2个1 示例2 输入： 0 ==复制== 输出： 0

计算一个数在二进制表示下1的个数，可以使用位运算的技巧。一种常用的方法是利用一个循环，每次循环都将该数与1进行位与操作（&），以检查最低位是否为1，然后将该数右移一位（\>\>）。循环直到该数变为0。此外，还有一个更高效的方法，即利用n & (n - 1)操作，该操作会将n的二进制表示中的最低位的1变为0，循环此操作直到n变为0，操作的次数就是n的二进制表示中1的个数。

以下是实现上述方法的Python代码：

方法1：常规位运算

def count_bits(n): count = 0 while n: count += n & 1 # 如果最低位是1，则计数加1 n >>= 1 # 将n右移一位 return count

多组输入

try: while True: n = int(input()) print(count_bits(n)) except EOFError: pass

方法2：n & (n - 1)技巧

def count_bits_fast(n): count = 0 while n: n &= n - 1 # 将n的最低位的1变为0 count += 1 return count

多组输入

try: while True: n = int(input()) print(count_bits_fast(n)) except EOFError: pass

这两种方法都可以计算出一个数的二进制表示中1的个数。第二种方法count_bits_fast因为每次操作都直接将最低位的1变为0，所以在实践中通常更快。这两种方法都可以处理多组输入，直到输入结束。

详细讲解 我们可以分解一下这个过程。

假设n的二进制表示中有k个1，我们来看看n和n-1的二进制表示有什么区别：

1. 对于n，它的二进制表示中最右边的1右边（如果有的话）都是0；
2. 当我们从n减去1时，最右边的1会变成0，并且这个1右边的所有0（如果有的话）都会变成1。

换句话说，n - 1操作会找到n的最右边的1，将它变成0，并且把这个1右边的所有0都变成1。

当我们执行n & (n - 1)时，实际上是将n的最低位的1和它右边的所有0进行了位与操作。由于0 & 1 = 0，n的最低位的1和它右边的所有0都会变成0，而其他位不变，这样就实现了将n的最低位的1变成0的效果。

例子

假设n = 12，其二进制表示为1100。

• n - 1 = 11，二进制表示为1011。
• 执行n & (n - 1)：1100 & 1011 = 1000。

可以看到，12（1100）的最低位的1（即第二位的1）变成了0，结果为8（1000）。

通过重复这个过程，直到n变为0，我们就能计算出n的二进制表示中有多少个1。这个方法非常高效，特别是对于大数来说，因为它直接跳过了那些为0的位，只对n的二进制表示中的1进行操作。